package q347;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * 347. 前k个高频元素
 */
public class Solution {

    public static class Element{
        int num;
        int count;

        public Element(int num, int count) {
            this.num = num;
            this.count = count;
        }
    }

    public int[] topKFrequent(int[] nums, int k) {

        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 1) + 1);
        }

        PriorityQueue<Element> priorityQueue = new PriorityQueue<>((e1, e2) -> e2.count - e1.count);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            Integer num = entry.getKey();
            Integer count = entry.getValue();
            priorityQueue.offer(new Element(num, count));
        }

        int[] rs = new int[k];
        for (int i = 0; i < k; i++) {
            Element element = priorityQueue.poll();
            rs[i] = element.num;
        }

        return rs;
    }
}
